package practice;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 生成哈夫曼树
 */
public class GenHuffmanTree {

    private static class Node {

        private final int value;

        private Node left;

        private Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            // 获取输入
            int[] arr = Arrays.stream(sc.nextLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            // 构建哈夫曼树
            Node root = buildHuffmanTree(arr);
            // 中序遍历
            inorderTraversal(root);
        }
    }

    private static Node buildHuffmanTree(int[] arr) {
        PriorityQueue<Node> pg = new PriorityQueue<>(Comparator.comparingInt(n -> n.value));
        for (int e : arr) {
            pg.add(new Node(e));
        }

        while (pg.size()>1) {
            Node left = pg.poll();
            Node right = pg.poll();
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;
            pg.add(parent);
        }
        return pg.poll();
    }

    private static void inorderTraversal(Node root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.value+ " ");
            inorderTraversal(root.right);
        }
    }
}
